package com.fanshuai.list;

import java.util.Iterator;

public class LinkedList<E> implements List<E> {
    class Node<E> {
        E data;
        Node<E> prev;
        Node<E> next;

        Node() {
            this.data = null;
            this.prev = null;
            this.next = null;
        }

        Node(E e) {
            this.data = e;
            this.prev = null;
            this.next = null;
        }
    }

    private Node<E> head;
    private Node<E> tail;
    private int size;

    public LinkedList() {
        Node<E> node = new Node<E>();
        this.head = node;
        this.tail = node;
        this.size = 0;
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public int capacity() {
        return Integer.MAX_VALUE;
    }

    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public void add(E e) {
        Node<E> node = new Node<>(e);
        tail.next = node;
        node.prev = tail;

        tail = node;
        size++;
    }

    @Override
    public void add(int index, E e) {
        if (index < 0 || index > size) {
            throw new IndexOutOfBoundsException("IndexOutOfBoundsException, index=" + index);
        }

        Node<E> node = new Node<>(e);
        Node<E> p = head;
        for (int i = 0; i < index; i++) {
            p = p.next;
        }

        Node<E> next = p.next;

        node.next = next;
        if (null != next) {
            next.prev = node;
        }

        node.prev = p;
        p.next = node;

        if (index == size) {
            tail = node;
        }
        size++;
    }

    @Override
    public void remove(E e) {
        Node<E> node = head.next;

        while (node != null) {
            if (node.data.equals(e)) {
                Node<E> pre = node.prev;
                Node<E> next = node.next;

                pre.next = next;
                if (next != null) {
                    next.prev = pre;
                }

                node.next = null;
                node.prev = null;
                node.data = null;
                size--;

                if (node == tail) {
                    tail = pre;
                }

                node = next;
            } else {
                node = node.next;
            }
        }
    }

    @Override
    public void removeByIndex(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("IndexOutOfBoundsException, index=" + index);
        }

        Node<E> node = head.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }

        Node<E> pre = node.prev;
        Node<E> next = node.next;

        pre.next = next;
        if (next != null) {
            next.prev = pre;
        }
        node.next = null;
        node.prev = null;
        node.data = null;

        if (node == tail) {
            tail = pre;
        }
        size--;
    }

    @Override
    public E get(int index) {
        if (index < 0 || index >= size) {
            throw new IndexOutOfBoundsException("IndexOutOfBoundsException, index=" + index);
        }

        Node<E> node = head.next;
        for (int i = 0; i < index; i++) {
            node = node.next;
        }

        return node.data;
    }

    @Override
    public int indexOf(E e) {
        Node<E> node = head.next;
        for (int i = 0; i < size; i++) {
            if (node.data.equals(e)) {
                return i;
            }

            node = node.next;
        }

        return -1;
    }

    @Override
    public void addAll(List<E> list) {
        for (E e : list) {
            add(e);
        }
    }

    @Override
    public void clear() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> node = head.next;

            @Override
            public boolean hasNext() {
                return node != null;
            }

            @Override
            public E next() {
                E e = node.data;
                node = node.next;
                return e;
            }
        };
    }

    @Override
    public String toString() {
        StringBuffer b = new StringBuffer();
        Node<E> node = head.next;
        while (node != null) {
            b.append(node.data).append(", ");

            node = node.next;
        }

        String s = b.toString();
        if (s.length() > 0) {
            s = s.substring(0, s.length() - 2);
        }

        return "LinkedList[" + s + "]";
    }
}
